{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "19ea68bf",
   "metadata": {},
   "source": [
    "# 习题\n",
    "## 习题11.4\n",
    "![image.png](./images/exercise4.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "453fb06c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "以start=2为起点stop=2为终点的所有路径的状态序列y的概率为：\n",
      "    路径为：2->1->2->1->2 概率为：0.21\n",
      "    路径为：2->2->1->1->2 概率为：0.175\n",
      "    路径为：2->2->1->2->2 概率为：0.175\n",
      "    路径为：2->1->2->2->2 概率为：0.13999999999999999\n",
      "    路径为：2->2->2->1->2 概率为：0.09\n",
      "    路径为：2->1->1->1->2 概率为：0.075\n",
      "    路径为：2->1->1->2->2 概率为：0.075\n",
      "    路径为：2->2->2->2->2 概率为：0.06\n",
      "概率最大[0.21]的状态序列为: 2->1->2->1->2\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "class CRFMatrix:\n",
    "    def __init__(self, M, start, stop):\n",
    "        # 随机矩阵\n",
    "        self.M = M\n",
    "        #\n",
    "        self.start = start\n",
    "        self.stop = stop\n",
    "        self.path_prob = None\n",
    "\n",
    "    def _create_path(self):\n",
    "        \"\"\"按照图11.6的状态路径图，生成路径\"\"\"\n",
    "        # 初始化start结点\n",
    "        path = [self.start]\n",
    "        for i in range(1, len(self.M)):\n",
    "            paths = []\n",
    "            # 迭代变量是 _ 和 r。这里使用了元组解包来接收 enumerate 产生的每个元组。\n",
    "            # _ 是一个常用的命名约定，表示这个变量将被忽略，因为我们不关心索引值。r 是实际关心的迭代变量，它代表 path 中的每个元素。\n",
    "            for _, r in enumerate(path):\n",
    "                temp = np.transpose(r)\n",
    "                # 添加状态结点1\n",
    "                paths.append(np.append(temp, 1))\n",
    "                # 添加状态结点2\n",
    "                paths.append(np.append(temp, 2))\n",
    "            path = paths.copy()\n",
    "\n",
    "        # 添加stop结点\n",
    "        path = [np.append(r, self.stop) for _, r in enumerate(path)]\n",
    "        return path\n",
    "\n",
    "    def fit(self):\n",
    "        path = self._create_path()\n",
    "        pr = []\n",
    "        for _, row in enumerate(path):\n",
    "            p = 1\n",
    "            for i in range(len(row) - 1):\n",
    "                a = row[i]\n",
    "                b = row[i + 1]\n",
    "                # 根据公式11.24，计算条件概率\n",
    "                p *= M[i][a - 1][b - 1]\n",
    "            pr.append((row.tolist(), p))\n",
    "        # 按照概率从大到小排列\n",
    "        pr = sorted(pr, key=lambda x: x[1], reverse=True)\n",
    "        self.path_prob = pr\n",
    "\n",
    "    def print(self):\n",
    "        # 打印结果\n",
    "        print(\"以start=%s为起点stop=%s为终点的所有路径的状态序列y的概率为：\" % (self.start, self.stop))\n",
    "        for path, p in self.path_prob:\n",
    "            print(\"    路径为：\" + \"->\".join([str(x) for x in path]), end=\" \")\n",
    "            print(\"概率为：\" + str(p))\n",
    "        print(\"概率最大[\" + str(self.path_prob[0][1]) + \"]的状态序列为:\",\n",
    "              \"->\".join([str(x) for x in self.path_prob[0][0]]))\n",
    "\n",
    "        \n",
    "        \n",
    "# 创建随机矩阵\n",
    "M1 = [[0, 0], [0.5, 0.5]]\n",
    "M2 = [[0.3, 0.7], [0.7, 0.3]]\n",
    "M3 = [[0.5, 0.5], [0.6, 0.4]]\n",
    "M4 = [[0, 1], [0, 1]]\n",
    "M = [M1, M2, M3, M4]\n",
    "# 构建条件随机场的矩阵模型\n",
    "crf = CRFMatrix(M=M, start=2, stop=2)\n",
    "# 得到所有路径的状态序列的概率\n",
    "crf.fit()\n",
    "# 打印结果\n",
    "crf.print()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
